The skyline problem [Divide and Conquer, BST, Heap]

Time: O(NLogN); Space: O(N); hard

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A),

write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where:

  • Li is the x coordinate of the left edge of the ith building

  • Ri is the x coordinate of the right edge of the ith building

  • Hi is its height. It is guaranteed that 0 <= Li, Ri <= INT_MAX, 0 < Hi <= INT_MAX, and Ri - Li > 0.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

Example 1:

Input: buildings =

[
    [2,9,10],
    [3,7,15],
    [5,12,12],
    [15,20,10],
    [19,24,8]
]

Output:

[
    [2, 10],
    [3, 15],
    [7, 12],
    [12, 0],
    [15, 10],
    [20, 8],
    [24, 0]
]

Explanation:

  • The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline.

A key point is the left endpoint of a horizontal line segment.

Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

Example 2:

Input: buildings =

[
    [1, 3, 3],
    [2, 4, 4],
    [5, 6, 1]
]

Output:

[
    [1, 3],
    [2, 4],
    [4, 0],
    [5, 1],
    [6, 0]
]

Explanation:

  • The buildings are look like this in the picture. The yellow part is buildings.

Example 3:

Input: buildings =

[
    [1, 4, 3],
    [6, 9, 5]
]

Output:

[
    [1, 3],
    [4, 0],
    [6, 5],
    [9, 0]
]

Explanation:

  • The buildings are look like this in the picture. The yellow part is buildings.

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].

  • The input list is already sorted in ascending order by the left x position Li.

  • The output list must be sorted by the x position.

  • There must be no consecutive horizontal lines of equal height in the output skyline.

    • For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable;

    • the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

### 1. Divide and conquer solution

[13]:

class Solution1(object):
    '''
    Divide and conquer solution
    :type buildings: dict(int[][])
    :rtype: dict(int[][])
    '''
    def getSkyline(self, buildings):
        start, end, height = 0, 1, 2
        intervals = self.ComputeSkylineInInterval(buildings, 0, len(buildings))

        res = []
        last_end = -1

        for interval in intervals:
            if last_end != -1 and last_end < interval[start]:
                res.append([last_end, 0])
            res.append([interval[start], interval[height]])
            last_end = interval[end]

        if last_end != -1:
            res.append([last_end, 0])

        return res

    # Divide and Conquer
    def ComputeSkylineInInterval(self, buildings, left_endpoint, right_endpoint):

        if right_endpoint - left_endpoint <= 1:
            return buildings[left_endpoint:right_endpoint]

        mid = left_endpoint + ((right_endpoint - left_endpoint) // 2)

        left_skyline = self.ComputeSkylineInInterval(buildings, left_endpoint, mid)
        right_skyline = self.ComputeSkylineInInterval(buildings, mid, right_endpoint)

        return self.MergeSkylines(left_skyline, right_skyline)

    # Merge Sort
    def MergeSkylines(self, left_skyline, right_skyline):
        i, j = 0, 0
        start, end, height = 0, 1, 2
        merged = []

        while i < len(left_skyline) and j < len(right_skyline):
            if left_skyline[i][end] < right_skyline[j][start]:
                merged.append(left_skyline[i])
                i += 1
            elif right_skyline[j][end] < left_skyline[i][start]:
                merged.append(right_skyline[j])
                j += 1
            elif left_skyline[i][start] <= right_skyline[j][start]:
                i, j = self.MergeIntersectSkylines(merged, left_skyline[i], i,\
                                                   right_skyline[j], j)
            else: # left_skyline[i][start] > right_skyline[j][start].
                j, i = self.MergeIntersectSkylines(merged, right_skyline[j], j, \
                                                   left_skyline[i], i)

        # Insert the remaining skylines.
        merged += left_skyline[i:]
        merged += right_skyline[j:]
        return merged

    # a[start] <= b[start]
    def MergeIntersectSkylines(self, merged, a, a_idx, b, b_idx):
        start, end, height = 0, 1, 2
        if a[end] <= b[end]:
            if a[height] > b[height]:   # |aaa|
                if b[end] != a[end]:    # |abb|b
                    b[start] = a[end]
                    merged.append(a)
                    a_idx += 1
                else:             # aaa
                    b_idx += 1    # abb
            elif a[height] == b[height]:  # abb
                b[start] = a[start]       # abb
                a_idx += 1
            else:  # a[height] < b[height].
                if a[start] != b[start]:                            #    bb
                    merged.append([a[start], b[start], a[height]])  # |a|bb
                a_idx += 1
        else:  # a[end] > b[end].
            if a[height] >= b[height]:  # aaaa
                b_idx += 1              # abba
            else:
                #    |bb|
                # |a||bb|a
                if a[start] != b[start]:
                    merged.append([a[start], b[start], a[height]])
                a[start] = b[end]
                merged.append(b)
                b_idx += 1
        return a_idx, b_idx

[14]:

s = Solution1()
buildings = [
    [2,9,10],
    [3,7,15],
    [5,12,12],
    [15,20,10],
    [19,24,8]
]
assert s.getSkyline(buildings) == [
    [2, 10],
    [3, 15],
    [7, 12],
    [12, 0],
    [15, 10],
    [20, 8],
    [24, 0]
]

buildings = [
        [1, 3, 3],
        [2, 4, 4],
        [5, 6, 1]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [2, 4],
    [4, 0],
    [5, 1],
    [6, 0]
]

buildings = [
        [1, 4, 3],
        [6, 9, 5]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [4, 0],
    [6, 5],
    [9, 0]
]

[15]:

class Solution2(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        if not buildings:
            return []
        starts = {}
        ends = {}

        for l, r, h in buildings:
            if l not in starts:
                starts[l] = []
            if r not in ends:
                ends[r] = []
            starts[l].append(h)
            ends[r].append(h)
        points = list(set(list(starts.keys()) + list(ends.keys())))
        points.sort()

        skyline = []
        heights = [0]
        h = 0

        for i in points:
            for r in ends.get(i, []):
                heights.remove(r)
            heights.extend(starts.get(i, []))

            h_new = max(heights)
            if h != h_new:
                skyline.append([i, h_new])
                h = h_new

        return skyline

[16]:

s = Solution2()
buildings = [
    [2,9,10],
    [3,7,15],
    [5,12,12],
    [15,20,10],
    [19,24,8]
]
assert s.getSkyline(buildings) == [
    [2, 10],
    [3, 15],
    [7, 12],
    [12, 0],
    [15, 10],
    [20, 8],
    [24, 0]
]

buildings = [
        [1, 3, 3],
        [2, 4, 4],
        [5, 6, 1]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [2, 4],
    [4, 0],
    [5, 1],
    [6, 0]
]

buildings = [
        [1, 4, 3],
        [6, 9, 5]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [4, 0],
    [6, 5],
    [9, 0]
]

2. Using Heapq

[17]:

from heapq import heappush, heappop

class Solution3(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        # sort top left (-height), top right(height) points.
        points = []
        for b in buildings:
            l, r, h = b
            points.append((l,-h))
            points.append((r,h))
        points.sort()

        # scan from left to right
        heap = [] # h < 0 to make it max heap
        heappush(heap, 0) # for line on ground
        highest = 0
        keypoints = []
        lazyDelete = {} # h < 0
        for p in points:
            x, h = p
            # if h < 0, top left point, push to heap
            if h < 0:
                heappush(heap, h)

                # if highest point is updated, add it to key points queue
                if -heap[0] > highest:
                    keypoints.append([x, -heap[0]])
                    highest = -heap[0]
            # if h > 0, top right point, lazy delete
            else:
                if -h not in lazyDelete:
                    lazyDelete[-h] = 0
                lazyDelete[-h] += 1

                # check heap top, if it should be removed, remove it
                while (heap[0] in lazyDelete) and (lazyDelete[heap[0]] > 0):
                    lazyDelete[heap[0]] -= 1
                    heappop(heap)

                # if highest point is updated, add it to key points queue
                if -heap[0] != highest:
                    keypoints.append([x, -heap[0]])
                    highest = -heap[0]

        return keypoints

[18]:

s = Solution3()
buildings = [
    [2,9,10],
    [3,7,15],
    [5,12,12],
    [15,20,10],
    [19,24,8]
]
assert s.getSkyline(buildings) == [
    [2, 10],
    [3, 15],
    [7, 12],
    [12, 0],
    [15, 10],
    [20, 8],
    [24, 0]
]

buildings = [
        [1, 3, 3],
        [2, 4, 4],
        [5, 6, 1]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [2, 4],
    [4, 0],
    [5, 1],
    [6, 0]
]

buildings = [
        [1, 4, 3],
        [6, 9, 5]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [4, 0],
    [6, 5],
    [9, 0]
]

[19]:

import heapq

class Solution4(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        # add start-building events
        events = [(L, -H, R) for L, R, H in buildings]
        # also add end-building events(acts as buildings with 0 height)
        events += list({(R, 0, 0) for _, R, _ in buildings})
        # and sort the events in left -> right order
        events.sort()

        # events = sorted([(L, -H, R) for L, R, H in buildings] + list({(R, 0, None) for _, R, _ in buildings}))

        # res: result, [x, height]
        res = [[0, 0]]
        # live: heap, [-height, ending position]
        hp = [(0, float("inf"))]

        for x, negH, R in events:
            # 1, pop buildings that are already ended
            # 2, if it's the start-building event, make the building alive
            # 3, if previous keypoint height != current highest height, edit the result
            while x >= hp[0][1]:
                heapq.heappop(hp)
            if negH:
                heapq.heappush(hp, (negH, R))
            if res[-1][1] + hp[0][0]:
                res += [x, -hp[0][0]],

        return res[1:]

[20]:

s = Solution4()
buildings = [
    [2,9,10],
    [3,7,15],
    [5,12,12],
    [15,20,10],
    [19,24,8]
]
assert s.getSkyline(buildings) == [
    [2, 10],
    [3, 15],
    [7, 12],
    [12, 0],
    [15, 10],
    [20, 8],
    [24, 0]
]

buildings = [
        [1, 3, 3],
        [2, 4, 4],
        [5, 6, 1]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [2, 4],
    [4, 0],
    [5, 1],
    [6, 0]
]

buildings = [
        [1, 4, 3],
        [6, 9, 5]
]
assert s.getSkyline(buildings) == [
    [1, 3],
    [4, 0],
    [6, 5],
    [9, 0]
]